package com.lmk.dsa.algorithm.graph.shortestPath;

import com.lmk.dsa.struct.commons.Edge;
import com.lmk.dsa.struct.graph.DenseGraph;

/**
 * 弗洛伊德（Floyd）算法能解决最短距离问题，但无法给出具体的寻路路径
 * @author LaoMake
 * @since 1.0
 */
public class Floyd {

    /** 用于表示无连接的值 */
    private int maxValue = 65535;

    /** 图 */
    private DenseGraph graph;

    /** 顶点的总数 */
    private int n;

    /** 最短路径距离表 */
    private Integer[][] dis;

    /** 到达目标顶点的前驱顶点 */
    private Integer[][] pre;


    public Floyd(DenseGraph graph) {
        this.graph = graph;
        this.n = graph.vertexSize();
        this.dis = new Integer[n][n];
        this.pre = new Integer[n][n];

        Edge[][] matrix = graph.getMatrix();
        Edge e;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pre[i][j] = i;
                e = matrix[i][j];
                if(e != null){
                    dis[i][j] = e.weight;
                }else{
                    dis[i][j] = maxValue;
                }
            }
        }

        shortestPath();
    }

    private void shortestPath(){
        int len = 0;
        for (int k = 0; k < n; k++) { // 对中间顶点遍历
            for (int i = 0; i < n; i++) { // 对起始节点遍历
                for (int j = 0; j < n; j++) { // 对终点遍历
                    len = dis[i][k] + dis[k][j];
                    if(len < dis[i][j]){
                        dis[i][j] = len; // 更新最短距离
                        pre[i][j] = pre[k][j]; // 更显前驱节点
                    }
                }
            }
        }
    }
    /**
     * 获取从from到to的最短距离
     * @param from
     * @param to
     * @return
     */
    public int shortestPathTo(int from, int to) {
        return dis[from][to];
    }


    /**
     * 显示距离表
     */
    public void show(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(dis[i][j] + " ");
            }
            System.out.println();
        }
    }
}
